# 广度优先

"""给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :



返回其层序遍历:
[
     [1],
     [3,2,4],
     [5,6]
]

说明:
	1. 树的深度不会超过 1000。
	2. 树的节点总数不会超过 5000。
"""


class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children


class Solution:
    def leveOrder(self, root: Node) -> list[list[int]]:
        if not root:
            return []
        back = []
        cur_level = [[root]]
        while cur_level:
            temp = []
            next_level = []
            for i in cur_level:
                for j in i:
                    temp.append(j.val)
                    if j.children:
                        next_level.append(j.val)
            back.append(temp)
            cur_level = next_level
        return back


"""给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.
"""


class TreeNode1:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution1:
    def minDepth(self, root: TreeNode1) -> int:
        if root is None:
            return 0
        if root.left == None:
            return self.minDepth(root.right) + 1
        if root.right == None:
            return self.minDepth(self.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right))


class Solution2:
    def minDepth(self, root: TreeNode1) -> int:
        if not root:
            return 0
        t = [[root]]
        n = 1
        while True:
            tt = []
            for i in t[-1]:
                if not i.left and not i.right:
                    return n
                if i.left:
                    tt.append(i.left)
                if i.right:
                    tt.append(i.right)
            n += 1
            t.append(tt)
